package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/4 22:26
 */
public class J41 {

    static class MedianFinder {

        int[] nums;
        int size;
        int i;

        /** initialize your data structure here. */
        public MedianFinder() {
            nums = new int[50000];
        }

        public void addNum(int num) {
            size++;
            nums[i] = num;
            for (int j = i; j>0 && nums[j] < nums[j-1] ; j--) {
                nums[j] = nums[j] ^ nums[j-1];
                nums[j-1] = nums[j] ^ nums[j-1];
                nums[j] = nums[j] ^ nums[j-1];
            }
            i++;
        }

        public double findMedian() {
            int m = size/2;
            return size % 2 == 0? (double)(nums[m] + nums[m-1])/2: nums[m];
        }
    }


    // for test
    public static void main(String[] args) {
        // ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
        // [[],[1],[2],[],[3],[]]
        MedianFinder finder = new MedianFinder();
        finder.addNum(1);
        finder.addNum(2);
        System.out.println(finder.findMedian());
        finder.addNum(3);
        System.out.println(finder.findMedian());
    }

}
